package top.lcm668.study.oj.base.sortmethods;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: Coder-Lcm
 * @date: 2021/10/5 16:29
 * 基数排序，为了方便验证基数排序，T已经手动变成Integer类型了
 */
public class RadixSort<T extends Comparable<T>> extends BaseSort<T> {

    @Override
    protected void sort(T[] arr, boolean isAsc) {
        if (arr == null || arr.length < 2) {
            return;
        }
        Integer[] nums = (Integer[]) arr;
        // 1. 先取出最大数的位数
        Integer max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
        }

        int maxDigit = 0;
        while (max > 0) {
            max /= 10;
            maxDigit++;
        }

        int mod = 10, div = 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int i1 = 0; i1 < nums.length; i1++) {
                int num = (nums[i1] % mod) / div;
                bucketList.get(num).add(nums[i1]);
            }

            int index = 0;
            for (int i1 = 0; i1 < bucketList.size(); i1++) {
                for (int i2 = 0; i2 < bucketList.get(i1).size(); i2++) {
                    nums[index++] = bucketList.get(i1).get(i2);
                }
                bucketList.get(i1).clear();
            }
        }
        arr = (T[]) nums;
    }
}
